# 

# 

# ### Shortest Path算法详解与Python代码示例

# 

# #### 算法简介

# 

# 最短路径算法（Shortest Path Algorithm）是一类在图论中广泛应用的算法，主要用于解决在图中寻找两个节点之间最短路径的问题。这类算法在现实生活中的应用非常广泛，如导航系统中的路线规划、网络路由选择、社交网络分析等。

# 

# 最短路径算法可以分为单源最短路径算法和多源最短路径算法。单源最短路径算法是从一个源点出发，计算到图中所有其他节点的最短路径；而多源最短路径算法则是计算图中任意两个节点之间的最短路径。

# 

# 在众多最短路径算法中，Dijkstra算法和Floyd-Warshall算法是两种非常经典且常用的算法。这里我们主要介绍Dijkstra算法，并给出其Python代码示例。

# 

# #### Dijkstra算法详解

# 

# Dijkstra算法是一种贪心算法，用于解决带权重的有向图或无向图中的单源最短路径问题。算法的基本思想是：从源点开始，每次从未标记的节点中选择距离源点最近的节点，并标记为已访问，然后更新与该节点相邻的未访问节点的距离。重复这个过程，直到所有节点都被标记为已访问，此时就得到了从源点到所有其他节点的最短路径。

# 

# #### Python代码示例

# 

# 

import heapq



def dijkstra(graph, start):

    # 初始化距离字典，表示从起始点到每个节点的距离，默认为无穷大

    distance = {node: float('infinity') for node in graph}

    # 设置起始点到自身的距离为0

    distance[start] = 0

    # 使用最小堆来存储待处理的节点，格式为(距离, 节点)

    pq = [(0, start)]



    while pq:

        # 取出当前距离最小的节点

        current_distance, current_node = heapq.heappop(pq)



        # 如果当前节点的距离已经被更新过，则跳过

        if current_distance > distance[current_node]:

            continue



        # 遍历当前节点的所有邻居

        for neighbor, weight in graph[current_node].items():

            # 计算通过当前节点到达邻居的距离

            distance_through_current = current_distance + weight



            # 如果通过当前节点到达邻居的距离更短，则更新距离，并将邻居加入最小堆

            if distance_through_current < distance[neighbor]:

                distance[neighbor] = distance_through_current

                heapq.heappush(pq, (distance[neighbor], neighbor))



    return distance



# 示例图，表示节点之间的权重关系

graph = {

    'A': {'B': 1, 'C': 4},

    'B': {'A': 1, 'C': 2, 'D': 5},

    'C': {'A': 4, 'B': 2, 'D': 1},

    'D': {'B': 5, 'C': 1}

}



# 计算从节点'A'到图中所有其他节点的最短路径

print(dijkstra(graph, 'A'))  # 输出: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
